/*
 * @lc app=leetcode.cn id=208 lang=javascript
 *
 * [208] 实现 Trie (前缀树)
 */

// @lc code=start

// Tree Node
class TreeNode {
  constructor() {
    // 只有26个小写字母
    this.R = 26;

    this.value = null;
    this.next = new Array(this.R);
  }
}

/**
 * Initialize your data structure here.
 */
var Trie = function () {
  this.base = 'a'.charCodeAt();
  this.root = null;
  /**
   * @description: 查询是否存在key的节点
   * @param {TreeNode} x
   * @param {string} key
   * @param {number} deepth
   * @return {TreeNode} null,带value的node,不带value的node
   */
  this._search = (x, key, deepth) => {
    if (!x) return null;
    if (key.length === deepth) {
      return x;
    }
    const char = key.charCodeAt(deepth) - this.base;
    return this._search(x.next[char], key, deepth + 1);
  };
};

/**
 * Inserts a word into the trie.
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function (word) {
  const _insert = (x, key, value, deepth) => {
    if (!x) x = new TreeNode();
    if (key.length === deepth) {
      x.value = value;
      return x;
    }
    const char = key.charCodeAt(deepth) - this.base;
    x.next[char] = _insert(x.next[char], word, word, deepth + 1);
    return x;
  };

  this.root = _insert(this.root, word, word, 0);
};

/**
 * Returns if the word is in the trie.
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function (word) {
  // 如果返回的节点有value，那就代表查询到了
  const x = this._search(this.root, word, 0);
  if (x === null) return false;
  return x.value === null ? false : true;
};

/**
 * Returns if there is any word in the trie that starts with the given prefix.
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function (prefix) {
  const x = this._search(this.root, prefix, 0);

  return x === null ? false : true;
};

/**
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */
// @lc code=end
